1. Field of the Invention
The present invention relates generally to artificial intelligence and knowledge engineering, and more particularly to a digital computer for executing or interpreting a knowledge base to perform symbolic reasoning. The invention specifically relates to a knowledge system which enables its own knowledge and performance in problem solving to be compared to that of a student or expert for the purpose of providing instruction or evaluation.
2. Description of the Related Art
Knowledge systems are computer systems that emulate reasoning tasks by using an "inference engine" to interpret encoded knowledge of human experts stored in a "knowledge base". Knowledge systems are useful for problems that require diagnosis, recommendation, selection or classification. Such tasks in the past have been performed by human experts. If the domain of the knowledge base, or scope of the problem, is sufficiently narrow and a sufficiently large body of knowledge is properly encoded in the knowledge base, then the knowledge system can achieve performance matching or exceeding the ability of a human expert. In such a case the knowledge system becomes an "expert system".
The first step in building a knowledge system involves encoding unstructured and often unarticulated knowledge into machine readable form. For expert systems in a given application domain, several different kinds of knowledge are involved. The different kinds of knowledge include the vocabulary and structure of the domain, the judgmental knowledge of the domain, and the procedures or techniques by which the domain knowledge is applied to solve a specific problem. The vocabulary of the domain refers to the names of the individual objects and ideas that must be encoded in the knowledge base. The structure of the domain refers to relationships between the objects and the ideals in the domain. The judgmental knowledge of the domain refers to the rules of thumb or rules of inference which are used by human experts to solve a problem involving uncertain knowledge or to restrict the scope of relevant knowledge or to direct the search for solutions among various possibilities covered by the knowledge base. Therefore, to some extent the procedures or techniques by which the domain knowledge is applied are a part of the judgmental knowledge of the domain. The procedures or techniques, however, also include a good deal of knowledge that could be considered routine rather than judgmental, such as how to carry out a consultation with a user.
A user typically accesses knowledge in the knowledge system interactively during a consultation. It is important that the consultation occurs in a manner that assures the user that the knowledge in the knowledge base is being properly considered and applied. It is particularly important, for example, that the user is not asked for redundant information and is given specific reasons why the knowledge system arrives at particular conclusions.
Presently there are highly developed commercial tools which may be used by skilled knowledge engineers to build knowledge systems. The well-known commercial tools (such as KS300 manufactured by Teknowledge, Inc., 1850 Embarcadero Road, Palo Alto, California, 94303) are patterned after a tool called EMYCIN described in The Emycin Manual by Van Melle et al., Stanford University Report No. STAN-CS-81-885, Stanford, California, 94305 (October, 1981).
EMYCIN is specifically designed as a domain-independent system for constructing rule-based consultant expert system programs. Domain knowledge is represented in EMYCIN systems primarily as condition-action production rules which are applied according to a goal-directed backward chaining control procedure. Rules and consultation data are permitted to have associated measures of certainty, and incomplete data entry is allowed. The EMYCIN system includes an explanation facility that displays the line of reasoning followed by the consultation program, and answers questions from the user about the content of the knowledge base. When the user is asked for information, the user may respond by asking why information is being sought, and how information is known or will be found out.
EMYCIN also has special options called EXPLAIN, TEST and REVIEW for providing information at the end of the consultation about the values of selected groups of parameters. The parameters are selected by defining a variable named IMPORTANTPARMS. A condition may be specified that must be true in order for the option to have effect upon each group. The EXPLAIN option provides terse explanations about how the parameters' current values were concluded. With the TEST option specified, the system compares the current value of each parameter with a stored value for the case. REVIEW provides explanations, and if these are incorrect, helps the expert to locate the problems in the knowledge base.
A recognized shortcoming of the EMYCIN-based tools is that the high-level control knowledge about how to conduct a consultation is buried in the rules or is intermingled with definitions of objects and structures of the domain. As described in Erman et al., U.S. Pat. No. 4,658,370, this control knowledge should be made explicit by encoding it in an applicative an imperative procedural language defining control actions to be executed during interruption of a built-in control procedure at specified control steps. To provide transparent representation of control knowledge as well as factual knowledge, the knowledge base is preferably organized into distinct frames including the rules; control blocks separately encoding the control knowledge; and classes which become instantiated, attributes which take on values describing the class instances, class types, legal value hierarchies, and user defined functions, which all encode factual knowledge. The knowledge engineer may provide control blocks to be executed at the start of the consultation, after the instantiation of specified classes, when a value for a specified attribute is to be determined, after a specified attribute is determined, and upon explicit invocation by another control block.
The knowledge engineering tool described in Erman et al. U.S. Pat. No. 4,658,370 has been manufactured and sold by Teknowledge, Inc., 1850 Embarcadero Road, Palo Alto, Calif., 94303, under the trademakr "S.1". This knowledge engineering tool is intended for use by experienced knowledge engineers in building complex knowledge systems.
A knowledge engineering tool suitable for use by people with limited computer experience is described in Hardy et al. U.S. Pat. No. 4,648,044, herein incorporated by reference. Hardy discloses that because of the lack of knowledge engineering tools based on a transparent expert system language, a person needs a good deal of formal education in computer science as well as specialized training in knowledge engineering to become a skilled knowledge engineer. The term "expert system language" denotes the manner or way in which factual, judgmental and control knowledge is encoded in the knowledge base. Hardy et al. discloses a useful knowledge engineering tool for building an expert system and running a consultation on a personal-type microcomputer. The knowledge base language is easily understood because English-like language statements express facts, rules and meta-facts for specifying control knowledge, and control during a consultation is goal directed in depth-first fashion as specified by rule order. The tool includes interactive knowledge base debugging, question generation, legal response checking, explanation, and certainty factors. For the more experienced knowledge engineer, the tool permits the use of recursive rules and universally quantified variables.
The knowledge engineering tool described in Hardy et al. U.S. Pat. No. 4,648,044 has been manufactured and sold by Teknowledge, Inc., 1850 Embarcadero Road, Palo Alto, Calif., 94303, under the trademark "M.1". The current version of "M.1" provides a few additional features. The most significant of these includes a proposition called "do" for executing M.1 commands when applying a rule.
The above-mentioned knowledge system tools have been especially designed and widely used for constructing consultation systems which advise a user in a way which parallels the way that a human consultant advises a client. In this consultation mode, the system applies knowledge about how to solve a specified problem, and it also applies knowledge about how the consultation should be conducted with the user.
One field of application of knowledge systems is computer aided instruction, in which interactive computer programs are used for instigating and controlling learing. But a knowledge system that is an expert in a particular domain is not necessarily an expert teacher, since a good teacher must understand what the student is doing, not just what he is supposed do. A knowledge-based tutor should present a lesson optimized for each student, and should diagnose and correct a student's misunderstandings.
As described in A. Barr & E. Feigenbaum, The Handbook of Artificial Intelligence, Vol. 2, HeurisTech Press, Stanford, Calif. (1982) pp. 223-294, the main components of an intelligent computer-aided instruction (ICAI) system are problem solving expertise, a student model, and tutoring strategies. The problem solving expertise is the knowledge that the system tries to impart to the student. The student model is used to indicate what the student does and does not know. The tutoring strategies specify how the system presents material to the student.
On page 233 of Barr and Feigenbaum, supra, it is said that the tutoring module of ICAI systems must integrate knowledge about natural language dialogs, teaching methods, and the subject area. This is the module that communicates with the student, selecting problems for him to solve, monitoring and criticizing his performance, providing assistance upon request, and selecting remedial material. The design of this module involves issues such as when it is appropriate to offer a hint or how far the student should be allowed to go down the wrong track. This additional knowledge, beyond the representation for the subject domain and of the student's state of understanding, is knowledge of how to teach.
As described in Barr and Feigenbaum, supra, ICAI systems have been built which more or less demonstrate various parts of what would constitute a fully useable system.
A system called SCHOLAR by Jaime Carbonell concentrated on handling unanticipated student questions and generating instructional materials in varying levels of detail, according to the context of the dialog. The domain knowledge was represented in a semantic net separate from the tutor. A goal was to make the tutorial reasoning strategies independent of the domain being discussed.
A system called WHY by Alan Collins and Albert Stevens focussed on Socratic-style probing of causal relations, and attempted to reveal inadequacies in a student's general model of causal relations by selecting examples which violate rules the student has articulated.
SOPHIE (I, II and III) by John Seely Brown and Richard Burton permitted broad student initiative during tutorial interaction, and used numerous heuristic strategies for answering the student's questions, criticizing his hypotheses, and suggesting alternative theories for his current hypotheses. The original Sophie was extended by providing an articulate expert debugger or explainer having the capability to solve the problem as presented to the student and to explain reasoning or interpretation as data pertaining to the problem was given to the student. SOPHIE I, II and III are also described in Brown et al., "Pedagogical, Natural Language and Knowledge Engineering Techniques in SOPHIE I, II and III," Cognitive and Instructional Sciences, Xerox Palo Alto Research Center, REPRINTED IN Sleeman et al., eds., Intelligent Tutoring Systems, Academic Press (1981).
A system called the WUSOR/WUMPUS Tutor by Ira Goldstein described student knowledge in terms of expert rules by a use/appropriate ratio, and explained the reasoning of an expert when a student behaved differently. The system included four modules: the Expert, the Psychologist, the Student Model, and the Tutor. The Expert told the Psychologist if a player's move was nonoptimal and which skills were needed for the player to discover better alternatives. The Psychologist employed this comparison to formulate hypotheses concerning wich domain specific skills are known to the student. These hypotheses are recorded in the Student Model, which represents the student's knowledge as a subset of the Expert's skills. The Tutor uses the Student Model to guide its interactions with the player. Basically, it chooses to discuss skills not yet exhibited by the player in situations where their use would result in better moves.
A system called GUIDON by William J. Clancey demonstrated that teaching knowledge could be treated analogously to the domain expertise of consultation systems. The teaching knowledge was codified in rules and built incrementally by testing it on different cases. For encoding knowledge of the problem domain, GUIDON used the EMYCIN-type production rules of a consultation expert system called MYCIN designed for diagnosing infectious diseases. The MYCIN rules were separate from the teaching rules and they were not modified for the tutoring application but they were used in new ways, for example, for forming quizzes, guiding the dialog, summarizing the evidence, and modeling the student's understanding.
Sample interactions with GUIDON are shown on pages 268-270 and 273-274 of Barr and Feigenbaum, supra. The student asks for the data and subgoals relevant to the topic being discussed. These are extracted from MYCIN's rules. The student asks how a particular datum is useful. He is given the case specific information, and then a summary of its use in the rule or rules that apply in this case. The student indicates that he has determined a particular subgoal. If the student's response were not consistent with his claim, he would be asked to state his conclusion and then possibly support it. When the topic of discussion is completed, the student is given a summary of the relevant conclusions. "Key factors" from each rule are automatically extracted and only the "interesting" (useful) conclusions are displayed. GUIDON also probes the student to determine whether the student knows why an alternative hypothesis is discredited. GUIDON asks the student to state a hypothesis for a subgoal. The program asks the student to support his hypothesis. Factors received from the student are related to the MYCIN rules, and the student is told whether the factors are correct and is told about factors missed. Other hypotheses are then discussed.
Before a session with a student begins, a case to be presented to the student is selected from a case library, and GUIDON uses MYCIN to "solve" the case. The results of this background consultation are reconfigured so that the rules are indexed both by the goals that they conclude about and the subgoals or data needed to apply them. During the tutorial session, the student inquires and receives more case data, and the same information is used to drive the MYCIN rules in a forward direction. The record of what the expert (i.e., MYCIN) "knows" at any given time during the student-run consultation forms the basis for evaluating the student's partial solutions and providing assistance.
The operation of GUIDON is further described in William J. Clancey, "Tutoring Rules for Guiding a Case Method Dialog," appearing in Sleeman & Brown, eds., Intelligent Tutoring Systems, Academic Press, Inc. (1982) pp. 201-225, and William J. Clancey, "Methodology for Building an Intelligent Tutoring System," appearing in Kintsch et al., eds., Methods and Tactics in Cognitive Science, Lawrence Erlbaum Assoc., Chapter 3 (1984).
A LISP/GEOMETRY Tutor by John Anderson is described in Anderson et al., "The Geometry Tutor," Advanced Computer Tutoring Project, Carnegie-Mellon University. The program asks a student to solve a problem, and the program matches each student input against rules for ideal and inferior student behavior. The program corrects the student when the student's behavior deviates below a minimum threshold.